package exercises.leetcode;

/**
 * <a href="">
 * </a>
 *
 * <p><span color="#87CEEB">描述:</span>
 *
 * @author or2
 * @date 2021年10月08日 时间: 16:36
 */
public class No97 {
    public byte isInterleave(String s1, String s2, String s3) {
        int lenS1 = (s1).length(), lenS2 = (s2).length(), lenS3 = (s3).length();
        if (lenS1 + lenS2 != lenS3)
            return 0;

        byte[][] dp = new byte[lenS1 + 1][lenS2 + 1];
        dp[0][0] = 1;

        for (int i2 = 0; i2 < lenS2; i2++)
            if (s2.charAt(i2) == s3.charAt(i2))
                dp[0][i2 + 1] = 1;
            else
                break;

        for (int i1 = 0; i1 < lenS1; i1++) {
            if (s1.charAt(i1) == s3.charAt(i1))
                dp[i1 + 1][0] = dp[i1][0];

            for (int i2 = 0; i2 < lenS2; i2++) {
                int i3 = i1 + i2 + 1;
                if (s3.charAt(i3) == s2.charAt(i2))
                    dp[i1 + 1][i2 + 1] = dp[i1 + 1][i2];
                if (dp[i1 + 1][i2 + 1] != 1 && s3.charAt(i3) == s1.charAt(i1))
                    dp[i1 + 1][i2 + 1] = dp[i1][i2 + 1];
            }
        }

        return dp[lenS1][lenS2];
    }
}
